\documentclass[%
    a4paper,
    10pt,
    final,
    notitlepage,
    narroweqnarray,
    inline,
    oneside,
    article
    ]{ieee}

\usepackage[spanish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{epsfig}
\usepackage{epstopdf}

\newcommand{\latexiie}{\LaTeX2{\Large$_\varepsilon$}}

\begin{document}

\title[]{ \textsc{Entrega Preliminar 1\\ Algoritmos de b\'usqueda no informados} }

\author{
     Luciano Mangiarotti,
\and Federico Santos,
\and Jimena Pose
}

\maketitle

\section{Introducci\'on}

\noindent El objetivo de este trabajo es utilizar distintos algoritmos de b\'usqueda desinformados para resolver el problema asignado y analizar los resultados a partir de las caracter\'isticas de cada uno de los algoritmos.\\

\noindent El problema a resolver es el juego llamado \textit{CalcuDoku} \cite{1}. El mismo consiste en un tablero cuadrado de dimensi\'on $N$ que se debe completar con n\'umeros enteros entre 1 y $N$ cumpliendo las siguientes restricciones: \\

\begin{itemize}
  \item No puede repetirse el mismo entero en una fila.
  \item No puede repetirse el mismo entero en una columna.
  \item Deben cumplirse las restricciones aritm\'eticas indicadas en el tablero. \\
\end{itemize}

\noindent Las restricciones aritm\'eticas se aplican a grupos de celdas adyacentes, exigiendo que el resultado de aplicar una operaci\'on a dichas celdas sea igual a un valor dado.\\

\noindent Las operaciones aceptadas son la suma y el producto. Una celda puede formar parte de un solo grupo. Por ejemplo, los valores en $(0,0)$, $(0,1)$ y $(0,2)$ deben sumar $4$.\\

\noindent Los algoritmos de b\'usqueda desinformados a utilizar son DFS, BFS y Profundizaci\'on iterativa.\\

\noindent En la secci\'on II se trata el desarrollo del trabajo. Se explican las consideraciones que se tuvieron en cuenta para realizarlo y se comenta una posible funci\'on de costo y heur\'isticas para el problema. En la secci\'on III se muestran los resultados obtenidos con los distintos m\'etodos de b\'usqueda y se sacan las correspondientes conclusiones sobre dichos resultados. En la secci\'on IV se presentan los comentarios finales.

\section{Desarrollo}

\noindent Para el desarrollo del problema es importante analizar los estados y las reglas a utilizar. Adem\'as, sobre el final de la secci\'on se comenta una funci\'on de costo y dos posibles heur\'isticas para usar con algoritmos de b\'usqueda informados.\\

\noindent El estado de cada uno de los nodos se representa con una matriz de enteros de $N\times N$ celdas. Dos estados son iguales cuando tienen los mismos enteros en ex\'actamente la misma posici\'on del tablero.\\

\noindent En este problema la cantidad de reglas var\'ia de acuerdo a la dimensi\'on del tablero. En particular, la cantidad de reglas va a ser igual a $N^3$ ya que $N^2$ es la cantidad de celdas del tablero y a su vez $N$ es la cantidad de enteros que se pueden poner en una celda. A continuaci\'on se enumeran las 8 reglas correspondientes a un tablero de $2\times 2$: \\

\begin{itemize}
  \item Poner un 1 en la casilla [0,0] siempre y cuando este vac\'ia, cumpla las restricciones aritm\'eticas y no se repita en una fila o columna.
  \item Poner un 2 en la casilla [0,0] siempre y cuando este vac\'ia, cumpla las restricciones aritm\'eticas y no se repita en una fila o columna.
  \item Poner un 1 en la casilla [0,1] siempre y cuando este vac\'ia, cumpla las restricciones aritm\'eticas y no se repita en una fila o columna.
  \item Poner un 2 en la casilla [0,1] siempre y cuando este vac\'ia, cumpla las restricciones aritm\'eticas y no se repita en una fila o columna.
  \item Poner un 1 en la casilla [1,0] siempre y cuando este vac\'ia, cumpla las restricciones aritm\'eticas y no se repita en una fila o columna.
  \item Poner un 2 en la casilla [1,0] siempre y cuando este vac\'ia, cumpla las restricciones aritm\'eticas y no se repita en una fila o columna.
  \item Poner un 1 en la casilla [1,1] siempre y cuando este vac\'ia, cumpla las restricciones aritm\'eticas y no se repita en una fila o columna.
  \item Poner un 2 en la casilla [1,1] siempre y cuando este vac\'ia, cumpla las restricciones aritm\'eticas y no se repita en una fila o columna. \\
\end{itemize}

\noindent De la misma forma, en un tablero de 3x3 se tienen 27 reglas, mientras que en uno de 4x4 se tienen 64.

\subsection*{Funci\'on de costo y heur\'isticas}

\noindent Se propone como m\'etrica para determinar el costo de la b\'usqueda la cantidad de valores insertados en el tablero. Se asume que el estado inicial tiene costo igual a cero ya que est\'a vac\'io. El costo de aplicar una regla es unitario e igual en todos los casos.\\

\noindent Luego, cada vez que se pone un nuevo valor en el tablero se incrementa en uno el costo total. De acuerdo a esta m\'etrica, el costo del estado \textit{goal} es igual a la cantidad de celdas que tiene el tablero, es decir $N^2$.\\

\noindent Tambi\'en se proponen dos posibles heur\'isticas que permitan mejorar la soluci\'on del juego en cuesti\'on mediante el uso de algoritmos de b\'usqueda informados. Estas heur\'isticas se calculan en funci\'on de la distancia a la que se encuentra un determinado estado de la soluci\'on, o estado \textit{goal}. Cuanto se est\'a m\'as cerca de la soluci\'on menor es el valor de $h(n)$, siendo $0$ en el estado final.\\

\noindent Una posible primer heur\'istica para el presente problema consiste en determinar el valor de la funci\'on $h$ en dicho estado seg\'un la cantidad de bloques de restricciones aritm\'eticas que falten completar. Por ejemplo, para un tablero con cuatro grupos de celdas, de los cuales s\'olo uno se encuentra completo, la funci\'on heur\'istica ser\'a $h(n) = 3$.\\

\noindent A medida que se van completando los bloques, se acerca a la soluci\'on, y el valor de la heur\'istica disminuye. Para el estado \textit{goal}, todos los grupos de celdas est\'an completos y se tiene $h(n) = 0$.\\

\noindent Una segunda heur\'istica posible para el presente problema consiste en determinar el valor de $h(n)$ en un estado de acuerdo a la cantidad de filas y columnas que falten completar.\\

\noindent En un tablero de $3 \times 3$ que se encuentra vac\'io (estado inicial) la heur\'istica es $h(n_0) = 6$, ya que ninguna de las filas o columnas est\'an completas. A medida que se van completando las celdas, se est\'a m\'as cerca de la soluci\'on, y por lo tanto el valor de la funci\'on heur\'istica disminuye.

\section{Resultados y Conclusiones}

\noindent A continuaci\'on se muestran los resultados obtenidos utilizando los algoritmos de b\'usqueda desinformados propuestos. Las pruebas fueron realizadas utilizando tableros de $2 \times 2$, $3 \times 3$ y $4 \times 4$, con las restricciones especificadas en las siguientes secciones.

\subsection{Primera Prueba: Tablero de $2 \times 2$}

\noindent Para esta primera prueba se utiliz\'o el tablero m\'as pequeño posible, con s\'olamente 4 celdas. Las restricciones del mismo son las siguientes:\\

\begin{itemize}
  \item Las celdas $(0,0)$ y $(1,0)$ deben sumar 3.
  \item La celda $(0,1)$ debe valer 1.
  \item La celda $(1,1)$ debe valer 2. \\
\end{itemize}

\noindent A continuaci\'on se muestra un cuadro comparativo con los resultados obtenidos para cada uno de los tres algoritmos a analizados:

\begin{center}
    \begin{tabular}{l c c c}
    \hline
    \hline
     & \textbf{DFS} & \textbf{BFS} & \textbf{PI}\\
    \hline
    \hline
    \textbf{Nodos Expandidos} & 4 & 49 & 37\\
    \textbf{Nodos Frontera} & 9 & 23 & 9\\
    \textbf{Tiempo} & 5 ms & 11 ms & 9 ms\\
    \textbf{Estados Generados} & 13 & 72 & 91\\
    \end{tabular}
\end{center}

\noindent La soluci\'on se encuentra a nivel 4 en todos los algoritmos ya que el tablero tiene 4 celdas. Se puede concluir de este cuadro comparativo es que el algoritmo \textit{DFS} expande menor cantidad de nodos que los otros dos algoritmos. Esto se debe a que comienza expandiendo la rama donde est\'a la soluci\'on. En cambio \textit{BFS} va expandiendo todos los nodos de todos los niveles hasta llegar al cuarto, que es donde est\'a la soluci\'on.\\

\noindent Por su parte, \textit{Profundizaci\'on iterativa} expande menos nodos que \textit{BFS}, ya que el algoritmo procesa con profundidad 1, 2 y 3 sin encontrar la soluci\'on, hasta que la encuentra procesando con profundidad 4.

\subsection{Segunda Prueba: Tablero de $3 \times 3$}

\noindent Para esta segunda prueba se utiliz\'o un tablero con 9 celdas. Las restricciones del mismo son las siguientes:\\

\begin{itemize}
  \item Las celdas $(0,1)$, $(0,2)$ y $(1,2)$ deben sumar 7.
  \item Las celdas $(0,0)$, $(1,0)$ y $(1,1)$ deben sumar 5.
  \item Las celdas $(2,0)$, $(2,1)$ y $(2,2)$ deben sumar 6. \\
\end{itemize}

\noindent A continuaci\'on se muestra un cuadro comparativo con los resultados obtenidos para cada uno de los tres algoritmos a analizados:

\begin{center}
    \begin{tabular}{l c c c}
    \hline
    \hline
     & \textbf{DFS} & \textbf{BFS} & \textbf{PI}\\
    \hline
    \hline
    \textbf{Nod. Expand.} & 73516 & 3050336 & 4052931\\
    \textbf{Nod. Frontera} & 82 & 725759 & 82\\
    \textbf{Tiempo} & 5751 ms & 208083 ms & 271081 ms\\
    \textbf{Estados Gen.} & 73598 & 3776095 & 7103340\\
    \end{tabular}
\end{center}

\noindent Al igual que en la prueba anterior, el algoritmo \textit{DFS} expande una cantidad mucho menor de nodos que el resto de los algoritmos.\\

\noindent Se observa tambi\'en la diferencia de tiempo en el procesamiento, la cual es mucho m\'as elevada que en la primer prueba. En un tablero de estas dimensiones, se pone en evidencia que los algoritmos de fuerza bruta son m\'as ineficientes a medida que se incrementa el tama\~no del tablero.

\subsection{Tercera Prueba: Tablero de $4 \times 4$}

\noindent Para tableros de este tama\~no, resulta inviable encontrar la soluci\'on utilizando estos algoritmos, debido al tiempo de procesamiento requerido y la cantidad de memoria utilizada. Para este caso es inevitable la utilizaci\'on de algoritmos de  b\'usqueda informados.

\section{Comentarios Finales}

\noindent Se concluye que con los procesadores y cantidad de memoria que se tienen disponibles en una computadora actual, los tres algoritmos presentados en este informe logran resolver el problema hasta una dimensi\'on acotada, en particular $3\times3$. \\

\noindent Evidentemente, los algoritmos de b\'usqueda desinformados tienen ciertas limitaciones en estos casos, y para poder resolver tableros de mayores dimensiones ser\'a necesario el uso de algoritmos de b\'usqueda informados con sus respectivas heur\'isticas.


%Para concluir, se puede afirmar que los cuatro algoritmos de b\'usqueda mencionados en la secci\'on III logran resolver el problema, aunque con distintos tiempos de procesamiento y cantidad de nodos explotados, por eso es interesante %analizar las caracter\'isticas de cada uno de estos algoritmos para saber cu\'al utilizar en un determinado problema del que se desee hallar soluci\'on.\\
%El algoritmo de b\'usqueda \textit{Profundizaci\'on Iterativa} fue implementado y ejecutado, obteniendo un costo espacial id\'entico al \textit{BFS} y un costo temporal mucho mayor, teniendo en cuenta que en cada paso que no encuentra la %soluci\'on, se comienza nuevamente, y como se encontr\'o la soluci\'on \'optima a profundidad 36, se sab\'ia de antemano que el algoritmo iba a reiniciarse 35 veces, dando un costo temporal inaceptable. Debido a dicho costo temporal, no %se lleg\'o a finalizar la ejecuci\'on de \'este algoritmo, con lo cual la implementaci\'on del mismo fue descartada.


\begin{thebibliography}{1}
 \bibitem [1]{1} \textit{http://www.conceptispuzzles.com/index.aspx?uri=puzzle/calcudoku}
\end{thebibliography}

\clearpage

%\begin{figure}
%        \centering
%		\includegraphics[keepaspectratio=true]{fig1.png}
%        \caption{Estado inicial del juego. El cuadrado gris representa el vac\'io}
%        \label{g1}
%\end{figure}

\end{document}
